package offerbook;

import java.util.HashMap;
import java.util.Map;

/**
 * Created at 2019/11/1 0001 下午 3:44
 * 题目1：
 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 要求：时间O(n),空间O(1)
 * 题目2：
 * 一个整型数组里除了1个数字之外，其他的数字都出现了两次。请写程序找出这1个只出现一次的数字。
 * 方式1：遍历找，时间O(n²)，空间O(1)
 * 方式2：排序再找，时间O(nlogn)
 * 方式3：利用set，时空都是O(n)
 * 方式4：
 * 遍历nums 中的每一个元素
 * <p>
 * 如果某个nums 中的数字是新出现的，则将它添加到列表中
 * <p>
 * 如果某个数字已经在列表中，删除它
 * 方式5：任意两个相同的数异或，结果是0，任意一个数和0异或，结果不变。并且异或可以交换顺序。
 * 利用这个性质，把数组所有的数进行异或 ，最后所得的结果就是要找的数。
 * 时间O(n),空间O(1)
 */
public class Code40_FindAppearOnceInArray {

    /**
     * 先解决题目2，前三种方式略
     */
    public static int findAppear1_1(int[] arr) {
        //长度如果是偶数，不合法
        if (arr == null || arr.length == 0 || (arr.length & 1) == 0) {
            return 0;
        }
        int res = arr[0];
        for (int i = 1; i < arr.length; i++) {
            res = (res ^ arr[i]);
        }
        return res;
    }

    /**
     * 题目1：
     * <p>
     * 方式1： 通过
     * 利用题目2给定的思路，我们只要把数组分成两份，每份都只含一个不同的数字 ，问题就解决。
     * 先把arr所有元素异或，最后的结果肯定是最后两个出现一次的元素a和b异或的结果,记录为res = a ^ b。
     * res != 0 ,那么找到其二进制第一个不等于0的位置，比如indexBit = 3，a和b的第三位肯定一个是0一个是1.
     * 把arr所有元素按照indexBit位是否为1划分成两个数组。
     * 划分的数组有一下性质：
     * 成对出现的两个数必定在一个数组，因为indexBit为相等。
     * 两个出现一次的数不定在两个不同数组，因为indexBit不相等。
     * 再调用查找一个不等的数的方法，即可找到。
     *
     * @param num1 :num1[0]装第一个不同元素
     * @param num2 :num2[0]装第二个不同元素
     */
    public static void findAppear2_1(int[] arr, int[] num1, int[] num2) {
        //长度如果是奇数，不合法
        if (arr == null || arr.length == 0 || (arr.length & 1) != 0) {
            return;
        }
        int res = arr[0];
        for (int i = 1; i < arr.length; i++) {
            res ^= arr[i];
        }
        int bitIndex = 1;
        //找到res第一个不为0的位置，比如是第三位 ，那么bitIndex最后是100
        while ((res & bitIndex) == 0) {
            bitIndex = (bitIndex << 1);
        }
        //根据bitIndex位是否为1划分
        int res1 = 0;
        int res2 = 0;
        for (int i = 0; i < arr.length; i++) {
            //第arr[i]第bitIndex位是0
            if ((arr[i] & bitIndex) == 0) {
                res1 ^= arr[i];
            } else {
                res2 ^= arr[i];
            }
        }
        num1[0] = res1;
        num2[0] = res2;
    }

    /**
     * 方式2：利用Map,统计出现个数。时间O(n),空间O(n)
     */
    public static void findAppear2_2(int[] arr, int[] num1, int[] num2) {
        //长度如果是奇数，不合法
        if (arr == null || arr.length == 0 || (arr.length & 1) != 0) {
            return;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                map.put(arr[i], 2);
            }
        }
        //遍历map，找出为1个的。或者再次遍历数组
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (map.get(arr[i]) == 1) {
                if (count == 0) {
                    num1[0] = arr[i];
                    count++;
                } else {
                    num2[0] = arr[i];
                    return;
                }
            }
        }
    }



    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 6, 3, 2, 5, 5};
        findAppear1_1(arr);
    }
}
